//https://www.nowcoder.com/practice/965fef32cae14a17a8e86c76ffe3131f?tpId=13&tqId=2277604&ru=%2Fpractice%2Fcf7e25aa97c04cc1a68c8f040e71fb84&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//1.重要题目：1.前序遍历的升级版本，遍历到每个根节点；2.以当前节点为根节点，逐步往下走，看当前的路径和有没有等于当前sum；

#include <algorithm>
#include <climits>
#include <queue>
#include <vector>
#include <stack> 
#include <limits>

using namespace std;
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int res = 0;
    //dfs查询以某节点为根的路径数
    void dfs(TreeNode* root, int sum){ 
        if(root == NULL)
            return;
        //符合目标值
        if(sum == root->val) 
            res++;
        //进入子节点继续找
        dfs(root->left, sum - root->val); 
        dfs(root->right, sum - root->val);
    }
    //dfs 以每个节点作为根查询路径
    int FindPath(TreeNode* root, int sum) { 
        //为空则返回
        if(root == NULL) 
            return res;
        //查询以某节点为根的路径数
        dfs(root, sum); 
        //以其子节点为新根
        FindPath(root->left, sum); 
        FindPath(root->right, sum);
        return res;
    }
};
